A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of Invention
The present invention relates to the computation of time budgets. The present invention is more specifically related to the field of Computer-Aided Design (CAD) tools for automating the design and verification of electronic systems and circuits, and particularly the computation of time budgets.
2. Discussion of Background
Transistor placement (cells) and wire routing (nets) of a circuit design on a substrate has become an important area for computer-aided design (CAD). Advances in circuit integration have made it possible for circuit designers to incorporate designs having more than a million transistors on a single chip. Even using advanced CAD based approaches to place and route (PandR), circuit designs are complicated and both time and computationally intensive. Faster clock cycles and critical path constraints make the traditional process even more complicated.
A typical design process includes having a user design a logic circuit, and then direct a computer to program a logic device or to design a set of masks to implement the desired logic design. Timing of signals passed between parts of the logic device depends in part upon placement of the user""s circuit elements into transistor groups in the physical structure and the resultant arrangement of the metal wires. In general, longer wires mean longer delays, but the actual timing is also heavily dependent upon capacitances, resistances, which vary based on placement and proximity to other wires and circuit elements, and the number of logic elements a signal must traverse. In addition, as transistors have become faster, a larger percentage of the delay in passing a signal through the device is contributed by the wiring. Therefore it has become a worthwhile effort to select wiring segments carefully to minimize the delay caused by these wiring segments.
One problem is computing the net delay upper bounds. This problem consists of transforming design-level timing constraints (such as clock period) into local net delay constraints. These local net delay constraints are then used by the placer to do a timing driven placement, so they play a very important role in the final layout and performance. This problem has been already explored in the past, and there are some existing algorithms: Zero Slack Algorithm (ZSA), xe2x80x9cGeneration of Performance Constraints for Layoutxe2x80x9d Nair and co IEEE CAD 1989, MIMP, xe2x80x9cBounds on Net Delays for VLSI Circuitsxe2x80x9d Habib Youssef and co IEEE Transactions on Circuits and Systems November 1992, and LBA, xe2x80x9cIterative and Adaptative Slack Allocation for Performance-Driven Layout and FPGA Routingxe2x80x9d Jon Frankle DAC92.
Another previous system is described in xe2x80x9cA Delay Budgeting Algorithm Ensuring Maximum Flexibility in Placement,xe2x80x9d M. Sarrafzadeh, D. A. Knol, G. E. Tellez, IEEE transactions on CAD of Integrated Circuits and Systems November 1997. The method described here uses a Linear Programming formulation. However none of the above systems provide an optimal solution.
The present inventors have realized that existing solutions for determination of net delay constraints and budgets are inadequate. This invention presents a new approach to the problem of computing the net delay upper bounds.
The present invention is embodied as a method of computing a time budget for each edge in a Domain Restricted Timing Cone (DRTC) of a graph, comprising the steps of, determining timing constraints including a required output time (R) for an endpoint of the DRTC and an arrival time (Ai) for each input (i) of the DRTC, decorating each vertex in the graph with a time to endpoint (tte) value and a weight to endpoint (wte) value, tte representing a longest time to reach the endpoint and wte representing a largest sum of weight to reach the endpoint, computing a smallest slack to weight on each edge of the graph within the DRTC using the tte and wte pair for each edge.
The present invention also includes a method for performing analysis on a set of domain- restricted timing cones, comprising the steps of, selecting a domain restricted timing cone, determining a slack to weight ratio for each edge in the domain restricted timing cone, for each edge, if the determined slack to weight ratio for an edge is less than a current slack to weight ration for that edge, then, replacing the current slack to weight ratio with the current slack to weight ratio, and selecting a next domain restricted timing cone and repeating said steps of determining and replacing until each timing cone has been analyzed.
The present invention also includes A method of slack allocation within a timing graph, comprising the steps of, setting an initial edge time for each edge in the timing graph, and iteratively performing the following steps, computing an amount of the available slack to be budgeted to each edge of the graph, for each edge having a weight greater than zero, if the computed slack is greater than a predetermined epsilon, then restore the edge time to that in an immediately preceding iteration, and if the computed slack is less than or equal to the predetermined epsilon, then saving a current edge time and setting a weight of the edge to zero, stopping the iterative steps if an amount of slack to allocate is less than the predetermined epsilon, determining a new budget for each edge, and incrementing the edge time for each edge by the corresponding new budget, until the iterative steps are stopped or a maximum number of iterations is performed.
The invention may be embodied in a device and both the device and/or method may be conveniently implemented in programming on a general purpose computer, or networked computers, and the results are intended to be input to other devices or processes, such as timing driven placement, optimization, and so on, with the very end goal being to produce a chip. However, the results may also be displayed on an output device connected to any of the general purpose, networked computers, or transmitted to a remote device for output or display. In addition, any components of the present invention represented in a computer program, data sequences, and/or control signals may be embodied as an electronic signal broadcast (or transmitted) at any frequency in any medium including, but not limited to, wireless broadcasts, and transmissions over copper wire(s), fiber optic cable(s), co-ax cable(s), and opto-electric devices, etc.